class Solution {
public:
    unordered_map<int, int> ma, flag;
    int snakesAndLadders(vector<vector<int>>& board) {
        queue<pair<int, int>> que;
        int n = board.size();
        int x = n - 1, y = 0, num = 1, f = 1;
        while (num <= n * n)
        {
            ma[num] = board[x][y];
            num += 1;
            if (f && y != n - 1) y += 1;
            else if (!f && y) y -= 1;
            else
            {
                x -= 1;
                if (f) f = 0;
                else f = 1;
            }
        }
        que.push(pair<int, int>(1, 0));
        while (!que.empty())
        {
            pair<int, int> temp = que.front();
            que.pop();
            if (temp.first == n * n) return temp.second;
            for (int i = temp.first + 1; i <= min(n * n, temp.first + 6); i++)
            {
                if (flag[i]) continue;
                flag[i] = 1;
                int ne = i;
                if (ma[i] != -1) ne = ma[i];
                que.push(pair<int, int>(ne, temp.second + 1));
            }
        }
        return -1;
    }
};